package com.yc.algorithm.sort;

import java.util.Arrays;

/**
 * 排序的实现
 * 均按从小到大的排序方式实现，重点理解各个排序的规则
 */
public class SortDemo {


    public static void main(String[] args) {
        int[] arr = new int[]{3,2,5,1,6,23};

        SortDemo sd = new SortDemo();
        System.out.println("排序前：" + Arrays.toString(arr));
//        sd.bubbleSort(arr);
//        sd.selectSort(arr);
        sd.insertSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));


    }

    /**
     * 冒泡排序算法
     */
    public void bubbleSort(int[] arr) {
        boolean flag = false; // 优化冒泡排序字段
        for (int j=0; j<arr.length; j++) {
            for (int i=0; i<arr.length - 1 - j; i++) {
                if (arr[i] > arr[i+1]) {
                    // 满足条件则交换数据
                    flag = true;
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            // 做循环的判断，避免不必要的循环
            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }

        // 本质上就是多次循环比较
//        for (int i=0; i<arr.length - 1 - 0; i++) {
//            if (arr[i] > arr[i+1]) {
//                // 满足条件则交换数据
//                int temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//
//        for (int i=0; i<arr.length - 1 - 1; i++) {
//            if (arr[i] > arr[i+1]) {
//                // 满足条件则交换数据
//                int temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
//
//        for (int i=0; i<arr.length - 1 - 2; i++) {
//            if (arr[i] > arr[i+1]) {
//                // 满足条件则交换数据
//                int temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//            }
//        }
    }


    /**
     * 快排
     */
    public void quickSort(int[] arr){

    }

    /**
     * 选择排序
     * 思路：
     *  1. 一共有length - 1次循环
     *  2.首先假定第一数是最小数，然后和后面的每个数比较，发现有比当前更小的数就重新确定
     *  最小数，并得到下标。当遍历到最后时，就得到本轮最小数和下标交换。
     */
    public void selectSort(int[] arr) {
        for (int i=0; i<arr.length-1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j=i+1; j<arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 此处增加判断
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }

        }
    }

    /**
     * 插入排序
     * 分为有序表和无序表：
     *  有序表有 1 个元素
     *  无序表有 n-1 个元素
     * @param arr 待排序的数组
     */
    public void insertSort(int[] arr) {
        int val = 0;
        int index = 0;
        for (int i=1; i<arr.length; i++) {
            val = arr[i];
            index = i - 1; // 即arr[1]的前面这个数的下标
            // 给insertVal 找到插入的位置
            // 说明
            // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            // 3. 就需要将 arr[insertIndex] 后移
            while (index >= 0 && val < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            // 当退出while循环时，说明插入的位置找到, insertIndex + 1
            // 举例：理解不了，我们一会 debug
            //这里我们判断是否需要赋值
            if(index + 1 != i) {
                arr[index + 1] = val;
            }
        }

    }


    /**
     * 堆排序
     * 大顶堆概念的理解和使用
     */
    public void heapSort(int[] arr) {



    }

    /**
     * 对数组进行堆调整，升序用大顶堆，降序用小顶堆
     * @param arr 待调整的数组
     * @param i 待调整的下标位置
     * @param length 需要调整的长度，一般为数组长度
     */
    private void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = i*2+1; k < length; k=k*2+1) {
            if (k+1 < length && arr[k] < arr[k+1]) {
                // 说明左子结点的值小于右子结点的值
                k++;
            }
            if (arr[k] > temp) {
                // 如果子节点大于父结点， 把较大的值赋给当前结点
                arr[i] = arr[k];
                i = k; // i指向k, 继续循环比较
            } else {
                break;
            }
        }
        // 当for循环执行结束后，我们已经以i 为父结点的树的最大值，放在了顶部
        // 将temp值放到调整后的位置
        arr[i] = temp;
    }

}
